package 合并K个升序链表23;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @author 谢阳
 * @version 1.8.0_131
 */

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                ", next=" + next +
                '}';
    }
}

class Solution {
    public static void main(String[] args) {
        ListNode listNode = new ListNode(1);
        listNode.next = new ListNode(4);
        listNode.next.next = new ListNode(5);
        ListNode listNode1 = new ListNode(1);
        listNode1.next = new ListNode(3);
        listNode1.next.next = new ListNode(4);
        ListNode listNode2 = new ListNode(2);
        listNode2.next = new ListNode(6);
        ListNode[] listNodes = new ListNode[]{listNode, listNode1, listNode2};
        ListNode listNode3 = mergeKLists(listNodes);
        System.out.println(listNode3);
    }

    public static ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> heap = new PriorityQueue<>(Comparator.comparingInt(o -> o.val));
        for (ListNode list : lists) {
            if (list != null) {
                heap.offer(list);
            }
        }
        ListNode res = new ListNode(0), cur = res;

        while (!heap.isEmpty()) {
            ListNode top = heap.poll();
            cur.next = top;
            cur = cur.next;
            if (top.next != null) {
                heap.offer(top.next);
            }
        }
        return res.next;
    }
}